import java.util.Arrays;

public class demo16 {
    public static void main(String[] args) {
        /*
         * 利用二分法在一个已经排序的数组中查找元素
         * */
        int[] arr = {1, 3, 9, 5, 6, 7, 1, 5, 4, 8,69};
        //首先对数组排序
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        //系统提供的二分法
        //int binarySearch = Arrays.binarySearch(arr, 77);
        //System.out.println(binarySearch);


        //自定义二分法
        int start = 0;
        int end = arr.length - 1;
        int key = 69;
        int index = -1;
        while (start <= end) {
            //确定中间数
            int mid = (start + end) >>> 1; //这个数组的中间下标
            //获取这个下标对应的数值
            int target = arr[mid];
            if (target > key){ //排除右边
                end = mid - 1;
            } else if (target < key) { //排除左边
                start = mid + 1;
            } else {
                index = mid;
                break;
            }
        }
        if (index == -1) {
            System.out.println("数组中没有这个值");
        } else {
            System.out.println("这个数在下标：" + index);
        }
    }
}
